package list;

import util.DLListPair;

public class DLList {
	
	DLNode dummy;
	int n;
	public DLList() {
		dummy=new DLNode();
		dummy.next=dummy;
		dummy.prev=dummy;
		n=0;
	}
	
	public DLNode getNode(int i){
		if(n==0){
			throw new IllegalArgumentException();
		}else{
			//continue
		}
		DLNode result;
		if(i<n/2){
			result=dummy.next;
			for(int index=0; index<i; index++){
				result=result.next;
			}
		}else{
			result=dummy.prev;
			for(int index=n-1; index>i; index--){
				result=result.prev;
			}
			
		}
		return result;
	}
	
	public void addBefore(DLNode node, String x) {
		DLNode newNode = new DLNode();
		newNode.x = x;
		
		newNode.next = node;
		newNode.prev = node.prev;
		node.prev = newNode;
		newNode.prev.next = newNode;
		
		n++;
		
	}
	
	public void addBefore(int i, String x) {
		DLNode indexNode = this.getNode(i);
		
		this.addBefore(indexNode, x);
		
	}
	
	public String get(int i) {
		return this.getNode(i).x;
	}
	
	public void set(int i, String x) {
		this.getNode(i).x = x;
	}
	
	public void removeNode(DLNode node){
		node.prev.next=node.next;
		node.next.prev=node.prev;
		n--;
	}
	
	public String remove(int i){
		DLNode node=this.getNode(i);
		String result=node.x;
		this.removeNode(node);
		return result;
	}
	
	public String toString(){
		String result="[";
		DLNode node=dummy;
		while(node.next!=dummy){
			node=node.next;
			result+=" "+node.x;
		}
		result+=" ]";
		return result;
	}
	/**
	 * Splits this list at a point before given node.
	 */
	public static DLListPair split(DLList list){
		if(list.n<2){
			throw new UnsupportedOperationException();
		}else{
			//there are at least two nodes, continue
		}
		//the last element of first list will be at splitIndex
		int splitIndex=list.n/2;
		DLNode splitNode=list.getNode(splitIndex-1);
		
		//create second list
		DLList secondList=new DLList();
		DLNode secondListHead=splitNode.next;		
		DLNode secondListDummy=new DLNode();
		secondListDummy.next=secondListHead;
		secondListHead.prev=secondListDummy;
		DLNode secondListTail=list.dummy.prev;
		secondListTail.next=secondListDummy;
		secondListDummy.prev=secondListTail;
		secondList.dummy=secondListDummy;
		secondList.n=list.n-splitIndex;
		
		//make original list first list
		
		splitNode.next=list.dummy;
		list.dummy.prev=splitNode;
		list.n=splitIndex;
		
		DLListPair<DLList> pair=new DLListPair<DLList>(list, secondList);
		return pair;
		
		
		
	}
	
	public void add(String x){
		this.addBefore(dummy, x);
	}

}
